While clustering has been one of the most effective tools for exploratory data mining for decades, it is widely accepted that the clusters generated without any supervision often do not lead to meaningful insights for the user. Accordingly, there has been a lot of interest in developing semi-supervised clustering models that can accommodate supervision from the user to guide the clustering process. In the most popular model for semi-supervised clustering, the user provides must-link and cannot-link constraints over pairs of data instances. It has been shown that such constraints can significantly improve clustering performance beyond that of unsupervised models.